﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.DynamicProgramming
{
    class BaseProblem
    {
        //=============================================力扣509 菲波拉契数
        //斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
        //给你 n ，请计算 F(n) 。
        public int Fib(int n)
        {
            if (n <= 1)
                return n;
            //dp[i]的定义为：第i个数的斐波那契数值是dp[i]
            int[] dp = new int[n];
            //dp数组初始化
            dp[0] = 0;
            dp[1] = 1;
            //遍历顺序
            for(int i = 2;i<=n;i++)
            {
                //状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }

        //================================================力扣70 爬楼梯
        //假设你正在爬楼梯，需要n阶你才能到达楼顶
        //每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶
        //注意：给定的n是一个正整数
        public int ClimbStairs(int n)
        {
            //dp[i]： 爬到第i层楼梯，有dp[i]种方法
            //首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
            //还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
            //所以dp[i] = dp[i - 1] + dp[i - 2] 。
            if (n <= 2)
                return n;
            int[] dp = new int[n+1];

            dp[1] = 1;
            dp[2] = 2;
            for(int i = 3;i<=n;i++)
            {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }

        //===================================================力扣746 使用最小花费爬楼梯
        //数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
        //每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
        //请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
        public int MinCostClimbingStairs(int[] cost)
        {
            //dp[i]:到达第i个台阶所花费的最少体力为dp[i].这里认为第一步是一定要花费的
            //dp[i] = min(dp[i-1],dp[i-2])+cost[i];

            int len = cost.Length;
            int[] dp = new int[len];
            //初始化
            dp[0] = cost[0];
            dp[1] = cost[1];

            for(int i = 2;i<len;i++)
            {
                dp[i] = Math.Min(dp[i - 1], dp[i - 2]) + cost[i];
            }
             // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
            return Math.Min(dp[len - 1], dp[len - 2]);//
        }

        //====================================================力扣62 不同路径
        //一个机器人位于一个m*n网格的左上角（起始点标记为start）
        //机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（标为finish）
        //问总共有多少条不同路径
        public int UniquePaths(int m, int n)
        {
            //dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
            //dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

            int[,] dp = new int[m, n];
            for (int i = 0; i < m; i++)
                dp[i,0] = 1;
            for (int j = 0; j < n; j++)
                dp[0,j] = 1;

            for(int i = 1;i<m;i++)
            {
                for(int j = 1;j<n;j++)
                {
                    dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
                }
            }
            return dp[m - 1, n - 1];

        }

        //===============================================力扣63 不同路径2
        //一个机器人位于一个m*n网格的左上角（起始点标记为start）
        //机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（标为finish）
        //现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
        //网格中的障碍物和空位置分别用 1 和 0 来表示。
        public int UniquePathsWithObstacles(int[][] obstacleGrid)
        {
            //dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
            //dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

            int m = obstacleGrid.Length;
            int n = obstacleGrid[0].Length;
            int[,] dp = new int[m, n];
            for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++)
            {//for循环的终止条件，一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理
                dp[i, 0] = 1;
            }
            for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) 
            {
                dp[0, j] = 1;
            }

            for(int i = 1;i<m;i++)
            {
                for(int j = 1;j<n;j++)
                {
                    if (obstacleGrid[i][j] == 1)
                        continue;
                    dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
                }
            }
            return dp[m - 1, n - 1];
        }

        //=============================================力扣343 整数拆分
        //给定一个正整数n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大
        //返回你可以获得的最大乘积
        public int IntegerBreak(int n)
        {
            //dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
            //从1遍历j,dp[i] = j * i-j;dp[i] = j* dp[i-j](相当于拆分i-j)
            int[] dp = new int[n+1];
            dp[2] = 1;

            for(int i = 3;i<=n;i++)
            {
                for(int j = 1;j<i-1;j++)
                {
                    dp[i] = Math.Max(dp[i], Math.Max((i - j) * j, dp[i - j] * j));
                }
            }
            return dp[n];
        }
        public int IntergerBreak_2(int n)
        {//用贪心，每次拆成n个3，如果剩下是4，则保留4，然后相乘，但是这个结论需要数学证明其合理性！
            if (n == 2)
                return 1;
            if (n == 3)
                return 2;
            if (n == 4)
                return 4;
            int result = 1;
            while(n > 4)
            {
                result *= 3;
                n -= 3;
            }
            result *= n;
            return result;
        }
    }
}
